/*
https://leetcode-cn.com/problems/profitable-schemes/solution/ying-li-ji-hua-by-leetcode-solution-3t8o/
 */
public class Solution879 {
    private static final int mod = 1000000007;
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int[][][] f=new int[group.length+1][n+1][minProfit+1];
        f[0][0][0]=1;
        for (int i=1;i<=group.length;i++){
            for (int j=0;j<=n;j++){
                for (int k=0;k<=minProfit;k++){
                    f[i][j][k]=f[i-1][j][k];
                    if (j>=group[i-1]){
                        f[i][j][k]=(f[i][j][k]+f[i-1][j-group[i-1]][Math.max(0,k-profit[i-1])])%mod;
                    }
                }
            }
        }
        int ans=0;
        for (int j=0;j<=n;j++){
            ans=(ans+f[group.length][j][minProfit])%mod;
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution879().profitableSchemes(5,3,new int[]{2,2},new int[]{2,3}));
    }
}
